// https://www.lintcode.com/problem/120/
// 转换为简单图上的最短路

class Solution {
public:
    /*
     * @param start: a string
     * @param end: a string
     * @param dict: a set of string
     * @return: An integer
     */
    int ladderLength(string &start, string &end, unordered_set<string> &dict) {
        queue<string> q;
        int cnt = 2;
        q.push(start); //别忘了！！
        dict.erase(start);
        while (!q.empty()) {
            int len = q.size();
            for (int l = 0; l < len; ++l) {
                string tmp = q.front();
                q.pop();
                for (int i = 0; i < tmp.length(); ++i) {
                    char t = tmp[i];
                    for (char j = 'a'; j <= 'z'; ++j) {
                        if (j != t) {
                            tmp[i] = j;
                            if (tmp == end) {
                                return cnt;
                            }
                            if (dict.find(tmp) != dict.end()) {
                                q.push(tmp);
                                dict.erase(tmp); //重要！防止重复
                            }
                            else {
                                tmp[i] = t;
                            }
                        }
                    }
                }
            }
            cnt++;
        }
        return 0;
    }
};